package com.copa.l448;

import java.util.ArrayList;
import java.util.List;

/**
 * @author copa
 * @createDate 2022-08-07 11:28
 * @function 原地修改
 */
public class Test1 {

    // 这是我一开始所想到的，但是呢超出时间限制啦，不可用
//    public List<Integer> findDisappearedNumbers(int[] nums) {
//        List<Integer> result = new ArrayList<>();
//        for (int i = 1; i <= nums.length; i++) {
//            result.add(i);
//        }
//        for (int num : nums) {
//            result.removeIf(n -> n == num);
//        }
//        return result;
//    }

    public List<Integer> findDisappearedNumbers(int[] nums) {
        int length = nums.length;
        for (int num : nums) {
            // 原地修改，(num - 1) % length对应的是该数所在的索引，如果存在直接加总数，证明该数存在
            // nums[i]实际上是当哈希表用了，因为题目有要求
            nums[(num - 1) % length] += length;
        }
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] <= length) {
                // 如果所遍历索引没有大于数组长度（因为上面存在的数都加上数组长度，所以必然大于数组长度）
                // 那么就添加该索引+1的数，这个数就是消失的数
                result.add(i + 1);
            }
        }
        return result;
    }


    public static void main(String[] args) {
        int[] nums = {4,3,2,7,8,2,3,1};
        //int[] nums = {1,1};
        List<Integer> result = new Test1().findDisappearedNumbers(nums);
        for (Integer num : result) {
            System.out.print(num + "\t");
        }
    }
}
